package eharmony;

import java.util.HashMap;
import java.util.HashSet;
import java.util.Map;
import java.util.Set;

public class Solution {

	public static void main(String[] args) {
		Solution s = new Solution();

//		int num = 5;
//		int[] arr = new int[num];
//		for (int i = 0; i < num; ++i) {
//			arr[i] = (int) ((Math.random() - 0.5)
//					* ((long)Integer.MAX_VALUE - Integer.MIN_VALUE));
//			System.out.print(arr[i]+" ");
//		}
		 int[] arr = new int[] {-1,0,2,2,3,3,3,6,7,8,9};
		System.out.println();

		System.out.println(s.equalization_steps(arr));
		System.out.println(s.longest_quasiconst_subseq(arr));
	}

	public int longest_quasiconst_subseq(int[] A) {
		if (A == null)
			return 0;

		Map<Integer, Integer> countMap = new HashMap<Integer, Integer>();

		for (int i = 0; i < A.length; ++i) {
			if (countMap.containsKey(A[i]))
				countMap.put(A[i], countMap.get(A[i]) + 1);
			else
				countMap.put(A[i], 1);

		}

		Set<Integer> evaluated = new HashSet<Integer>();

		int curLongest = 1;
		for (Integer val : countMap.keySet()) {
			if (countMap.containsKey(val - 1) && !evaluated.contains(val - 1)) {
				curLongest = Math.max(curLongest,
						countMap.get(val) + countMap.get(val - 1));
				evaluated.add(val - 1);
			}
			if (countMap.containsKey(val + 1) && evaluated.contains(val)) {
				curLongest = Math.max(curLongest,
						countMap.get(val) + countMap.get(val + 1));
				evaluated.add(val);
			}

		}
		return curLongest;
	}

	public int equalization_steps(int[] A) {
		if (A == null || A.length == 0)
			return -1;

		int maskResult = (A[0] & 0x1) == 0x1 ? 0x1 : 0x0;

		int min = A[0];
		int max = A[0];
		for (int i = 1; i < A.length; ++i) {
			if ((A[i] & 0x1) != maskResult)
				return -1;
			if (A[i] < min)
				min = A[i];
			if (A[i] > max)
				max = A[i];
		}

		return (int)((long)max - min) / 2;
	}
}
